package algorithm.leetcode.I201to400;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 实现超大稀疏矩阵的乘法
 *
 * Input:
 * A = [[1,0,0], [-1,0,3]]
 * B = [[7,0,0], [0,0,0], [0,0,1]]
 *
 * Output:
 * A*B = [[7,0,0], [-7,0,3]]
 *
 * 避坑:
 * map中的key不可以用二维数组,因为数组是引用对象
 * 下面的代码片段打印结果是null
 * HashMap<int[], Integer> res = new HashMap<>();
 * res.put(new int[]{1, 2}, 2);
 * System.out.println(res.get(new int[]{1, 2}));
 */


public class Q311 {

    public int[][] multiply(int[][] A, int[][] B) {
        Map<String, Integer> denseA = denseEncode(A);
        Map<String, Integer> denseB = denseEncode(B);
        Map<String, Integer> denseRes = new HashMap<>();
        int row = A.length;
        int col = B[0].length;

        for (Map.Entry<String, Integer> entry : denseA.entrySet()) {
            String[] rowAndCol = entry.getKey().split("#");
            int i = Integer.parseInt(rowAndCol[0]);
            int j = Integer.parseInt(rowAndCol[1]);
            for (int k = 0; k < col; k++) {
                if (denseB.containsKey(j+"#"+k)) {
                    int add = denseA.get(i+"#"+j) * denseB.get(j+"#"+k);
                    denseRes.put(i+"#"+k, denseRes.getOrDefault(i+"#"+k, 0) + add);
                }
            }
        }
        return sparseDecode(denseRes, row, col);
    }


    /**
     * 用稠密方法表示二维矩阵(参考tf中的sparse vector)
     * map中的key:非0元素的位置
     * map中的value:非0元素的值
     * @param matrix
     * @return
     */
    public Map<String, Integer> denseEncode(int[][] matrix) {
        HashMap<String, Integer> res = new HashMap<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] != 0) res.put(i+"#"+j, matrix[i][j]);
            }
        }
        return res;
    }

    /**
     * denseEncode的逆变换
     * @param dense
     * @param row
     * @param col
     * @return
     */
    public int[][] sparseDecode(Map<String, Integer> dense, int row, int col) {
        int[][] res = new int[row][col];
        for (Map.Entry<String, Integer> entry : dense.entrySet()) {
            String[] rowAndCol = entry.getKey().split("#");
            int i = Integer.parseInt(rowAndCol[0]);
            int j = Integer.parseInt(rowAndCol[1]);
            res[i][j] = entry.getValue();
        }
        return res;
    }

    public static void main(String[] args) {
        Q311 q311 = new Q311();
        int[][] a = new int[][]{new int[]{1,0,0}, new int[]{-1,0,3}};
        int[][] b = new int[][]{new int[]{7,0,0}, new int[]{0,0,0}, new int[]{0,0,1}};
        int[][] multiply = q311.multiply(a, b);
        for (int[] ints : multiply) {
            System.out.println(Arrays.toString(ints));
        }
    }

}
